package 刷题10月.二叉树;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
// https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/
public class 二叉树层次遍历515在每个树行中找最大值1003 {

     public class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
         }
     }

// 102.二叉树的层序遍历
    class Solution {
        public List<Integer> largestValues(TreeNode root) {
            //LinkedList实现队列
            Queue<TreeNode> queue = new LinkedList<>();
            List<Integer> values = new ArrayList<>();
            if (root != null)
                queue.add(root);//入队
            while (!queue.isEmpty()) {
                int max = Integer.MIN_VALUE;
                int levelSize = queue.size();//每一层的数量
                for (int i = 0; i < levelSize; i++) {
                    TreeNode node = queue.poll();//出队
                    max = Math.max(max, node.val);//记录每层的最大值
                    if (node.left != null)
                        queue.add(node.left);
                    if (node.right != null)
                        queue.add(node.right);
                }
                values.add(max);
            }
            return values;
        }


    }

}
